{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lowest Common Ancestor of a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lowestCommonAncestor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树的最近公共祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。</p>\n",
    "\n",
    "<p><a href=\"https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin\" target=\"_blank\">百度百科</a>中最近公共祖先的定义为：&ldquo;对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（<strong>一个节点也可以是它自己的祖先</strong>）。&rdquo;</p>\n",
    "\n",
    "<p>例如，给定如下二叉搜索树:&nbsp; root =&nbsp;[6,2,8,0,4,7,9,null,null,3,5]</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/binarysearchtree_improved.png\" style=\"height: 190px; width: 200px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8\n",
    "<strong>输出:</strong> 6 \n",
    "<strong>解释: </strong>节点 <code>2 </code>和节点 <code>8 </code>的最近公共祖先是 <code>6。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释: </strong>节点 <code>2</code> 和节点 <code>4</code> 的最近公共祖先是 <code>2</code>, 因为根据定义最近公共祖先节点可以为节点本身。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有节点的值都是唯一的。</li>\n",
    "\t<li>p、q 为不同节点且均存在于给定的二叉搜索树中。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lowest-common-ancestor-of-a-binary-search-tree](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lowest-common-ancestor-of-a-binary-search-tree](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,2,8,0,4,7,9,null,null,3,5]\\n2\\n8', '[6,2,8,0,4,7,9,null,null,3,5]\\n2\\n4', '[2,1]\\n2\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        # although it works, but it is very slow\n",
    "#         if p.left == q or p.right == q: return p\n",
    "#         if q.left == p or q.right == p: return q\n",
    "        \n",
    "#         queue = collections.deque([root])\n",
    "#         anc_dict = {}\n",
    "#         while queue:\n",
    "#             curr = queue.popleft()\n",
    "#             if curr.val not in anc_dict.keys():\n",
    "#                 anc_dict[curr.val] = [curr.val]\n",
    "#             if curr.left is not None:\n",
    "#                 anc_dict[curr.left.val] = [curr.left.val] + anc_dict[curr.val]\n",
    "#                 queue.append(curr.left)\n",
    "#             if curr.right is not None:\n",
    "#                 anc_dict[curr.right.val] = [curr.right.val] + anc_dict[curr.val]\n",
    "#                 queue.append(curr.right) \n",
    "#         if p.val in anc_dict[q.val]: return p\n",
    "#         if q.val in anc_dict[p.val]: return q\n",
    "#         i = -1\n",
    "#         while anc_dict[p.val][i] == anc_dict[q.val][i]:\n",
    "#             i -= 1\n",
    "#         return TreeNode(anc_dict[p.val][i+1])\n",
    "    \n",
    "#         # Value of current node or parent node.\n",
    "#         parent_val = root.val\n",
    "\n",
    "#         # Value of p\n",
    "#         p_val = p.val\n",
    "\n",
    "#         # Value of q\n",
    "#         q_val = q.val\n",
    "\n",
    "#         # If both p and q are greater than parent\n",
    "#         if p_val > parent_val and q_val > parent_val:    \n",
    "#             return self.lowestCommonAncestor(root.right, p, q)\n",
    "#         # If both p and q are lesser than parent\n",
    "#         elif p_val < parent_val and q_val < parent_val:    \n",
    "#             return self.lowestCommonAncestor(root.left, p, q)\n",
    "#         # We have found the split point, i.e. the LCA node.\n",
    "#         else:\n",
    "#             return root\n",
    "        \n",
    "        # Value of p\n",
    "        p_val = p.val\n",
    "\n",
    "        # Value of q\n",
    "        q_val = q.val\n",
    "\n",
    "        # Start from the root node of the tree\n",
    "        node = root\n",
    "\n",
    "        # Traverse the tree\n",
    "        while node:\n",
    "\n",
    "            # Value of current node or parent node.\n",
    "            parent_val = node.val\n",
    "\n",
    "            if p_val > parent_val and q_val > parent_val:    \n",
    "                # If both p and q are greater than parent\n",
    "                node = node.right\n",
    "            elif p_val < parent_val and q_val < parent_val:\n",
    "                # If both p and q are lesser than parent\n",
    "                node = node.left\n",
    "            else:\n",
    "                # We have found the split point, i.e. the LCA node.\n",
    "                return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if (p.val <= root.val and q.val >= root.val) or (p.val >= root.val and q.val <= root.val):\n",
    "            return root\n",
    "        elif p.val < root.val:\n",
    "            ret = self.lowestCommonAncestor(root.left, p, q)\n",
    "        else:\n",
    "            ret = self.lowestCommonAncestor(root.right, p, q)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if p.val < q.val:\n",
    "            return self._recursion(root, p, q)\n",
    "        else:\n",
    "            return self._recursion(root, q, p)\n",
    "\n",
    "    def _recursion(self, root, p, q):\n",
    "        if p.val <= root.val <= q.val: return root\n",
    "        if root.val < p.val and root.val < q.val:\n",
    "            return self._recursion(root.right, p, q)\n",
    "        if root.val > p.val and root.val > q.val:\n",
    "            return self._recursion(root.left, p, q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        path, cur = [root], root\n",
    "        while cur != p:\n",
    "            if cur.val > p.val:\n",
    "                cur = cur.left\n",
    "            elif cur.val < p.val:\n",
    "                cur = cur.right\n",
    "            path.append(cur)\n",
    "\n",
    "        for i in range(len(path)):\n",
    "            print(path[i].val)\n",
    "            \n",
    "        for i in range(len(path)):\n",
    "            node = path[i]\n",
    "            if node == p:\n",
    "                return p\n",
    "            if node.val > q.val:\n",
    "                node = node.left\n",
    "            elif node.val < q.val:\n",
    "                node = node.right\n",
    "            if node != path[i + 1]:\n",
    "                return path[i]\n",
    "            elif node == q:\n",
    "                return q\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "  def lowestCommonAncestor(self, root:TreeNode, p:TreeNode, q:TreeNode) -> TreeNode:\n",
    "    if root.val == p.val or root.val == q.val:\n",
    "      return root\n",
    "    val_to_path = defaultdict(list)\n",
    "    min_val = min(p.val, q.val)\n",
    "    max_val = max(p.val, q.val)\n",
    "    nodes = [root]\n",
    "    q_found = False\n",
    "    p_found = False\n",
    "    val_to_path[root.val] = [root]\n",
    "    while nodes:\n",
    "      node = nodes.pop(0)\n",
    "      if node.val == p.val:\n",
    "        p_found = True\n",
    "      elif node.val == q.val:\n",
    "        q_found = True\n",
    "      if p_found and q_found:\n",
    "        break\n",
    "      parent_path = val_to_path[node.val]\n",
    "      left = node.left\n",
    "      right = node.right\n",
    "      if node.val > min_val and left:\n",
    "        path = list(parent_path)\n",
    "        path.append(left)\n",
    "        val_to_path[left.val] = path\n",
    "        nodes.append(left)\n",
    "      if node.val < max_val and right:\n",
    "        path = list(parent_path)\n",
    "        path.append(right)\n",
    "        val_to_path[right.val] = path\n",
    "        nodes.append(right)\n",
    "\n",
    "\n",
    "    p_path = val_to_path[p.val]\n",
    "    q_path = val_to_path[q.val]\n",
    "    max_common_length = min(len(p_path), len(q_path))\n",
    "    for i in range(max_common_length-1, -1, -1):\n",
    "      if p_path[i].val == q_path[i].val:\n",
    "        return p_path[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        stack_p=[root]\n",
    "        stack_q=[root]\n",
    "        point=root\n",
    "        while point.val!=p.val:\n",
    "            if point.val<p.val:\n",
    "                point=point.right\n",
    "                stack_p.append(point)\n",
    "            else:\n",
    "                point=point.left\n",
    "                stack_p.append(point)\n",
    "        point=root\n",
    "        while point.val!=q.val:\n",
    "            if point.val<q.val:\n",
    "                point=point.right\n",
    "                stack_q.append(point)\n",
    "            else:\n",
    "                point=point.left\n",
    "                stack_q.append(point)\n",
    "        stack_p=stack_p[::-1]\n",
    "        print(stack_p)\n",
    "        for item in stack_p:\n",
    "            if item in stack_q:\n",
    "                return item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        parent = {}\n",
    "        def dfs(node, f):\n",
    "            nonlocal parent\n",
    "            parent[node] = f\n",
    "            if node.left:\n",
    "                dfs(node.left, node)\n",
    "            if node.right:\n",
    "                dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "        p_parent = []\n",
    "        while p in parent:\n",
    "            p_parent.append(p)\n",
    "            p = parent[p]\n",
    "        while q in parent and q not in p_parent:\n",
    "            q = parent[q]\n",
    "        return q\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        s = []\n",
    "        sp = []\n",
    "        sq = []\n",
    "        s.append(root)\n",
    "        while (len(s) != 0):\n",
    "            node = s[-1]\n",
    "\n",
    "            if node == p and len(sp) == 0:\n",
    "                sp = s.copy()\n",
    "            if node == q and len(sq) == 0:\n",
    "                sq = s.copy()\n",
    "\n",
    "            if len(sp) != 0 and len(sq) != 0:\n",
    "                break\n",
    "\n",
    "            if node.left != None:\n",
    "                s.append(node.left)\n",
    "                node.left = None\n",
    "                continue\n",
    "            elif node.right != None:\n",
    "                s.append(node.right)\n",
    "                node.right = None\n",
    "                continue\n",
    "            else:\n",
    "                s.pop()\n",
    "\n",
    "        sp = sp[::-1]\n",
    "        sq = sq[::-1]\n",
    "\n",
    "        for n in sp:\n",
    "            for nn in sq:\n",
    "                if n.val == nn.val:\n",
    "                    return n\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        if root == p:\n",
    "            return root\n",
    "        if root == q:\n",
    "            return root\n",
    "        root.left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        root.right = self.lowestCommonAncestor(root.right,p,q)\n",
    "        if not root.right:\n",
    "            return root.left\n",
    "        if not root.left:\n",
    "            return root.right\n",
    "        if root.left and root.right:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        while True:   \n",
    "            if root.val > q.val and root.val > p.val:\n",
    "                root = root.left\n",
    "            elif root.val < q.val and root.val < p.val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val > p.val and root.val > q.val:\n",
    "            return self.lowestCommonAncestor(root.left, p, q)\n",
    "        if root.val < p.val and root.val < q.val:\n",
    "            return self.lowestCommonAncestor(root.right, p, q)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q)\n",
    "        if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        root.left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        root.right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if not root.left: return root.right\n",
    "        if not root.right: return root.left\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        \n",
    "        root.left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        root.right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if root.left and root.right:\n",
    "            return root\n",
    "\n",
    "        if root.left:\n",
    "           return root.left\n",
    "        else:\n",
    "            return root.right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        \n",
    "\n",
    "        #  满足最近公共祖先的情况\n",
    "        # 1. p,q在root的两侧的子树\n",
    "        # 2. p=root,且q在root的左或右子树中\n",
    "        # 3. q=root,且p在root的左或右子树中\n",
    "        # 通过递归对二叉树进行先序遍历,当遇到p或q时返回,从下往上回溯,当P，q在root两侧时.root就是最近的公共祖先\n",
    "        # 递归终止条件:\n",
    "        # 1. 越过叶子节点\n",
    "        # 2. 当root等于P,q 直接返回root\n",
    "        # 先序递推\n",
    "        # \n",
    "\n",
    "        if not root or root==p or root==q:\n",
    "            return root\n",
    "\n",
    "        root.left = self.lowestCommonAncestor(root.left, p,q) # 递归左子节点\n",
    "        root.right = self.lowestCommonAncestor(root.right, p,q) # 递归右子节点\n",
    "\n",
    "        if not root.left and not root.right: # 左右同时不为空 说明pq在两侧 root为最近公共祖先\n",
    "            return\n",
    "        \n",
    "        if not root.left: # p,q 都不在root的左子树中 返回右(具体可分为两种：1,pq其中一个在柚子树中,2.pq都在)\n",
    "            return root.right\n",
    "        if not root.right:\n",
    "            return root.left\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        if root.val == p.val or root.val == q.val or not root:\n",
    "            return root\n",
    "        if root.val < p.val and root.val < q.val:\n",
    "            return self.lowestCommonAncestor(root.right,p,q)\n",
    "        elif root.val > p.val and root.val > q.val:\n",
    "            return self.lowestCommonAncestor(root.left, p, q)\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "\n",
    "        if root.val < min(p.val, q.val):\n",
    "            return self.lowestCommonAncestor(root.right, p, q)\n",
    "        elif root.val > max(p.val, q.val):\n",
    "            return self.lowestCommonAncestor(root.left, p, q)\n",
    "        else:\n",
    "\n",
    "            root.left = self.lowestCommonAncestor(root.left, p, q)\n",
    "            root.right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "            if root.left and root.right:\n",
    "                return root\n",
    "            if not root.left and not root.right:\n",
    "                return None\n",
    "            return root.left if root.left else root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "\n",
    "        if root.val < min(p.val, q.val):\n",
    "            return self.lowestCommonAncestor(root.right, p, q)\n",
    "        elif root.val > max(p.val, q.val):\n",
    "            return self.lowestCommonAncestor(root.left, p, q)\n",
    "        else:\n",
    "\n",
    "            root.left = self.lowestCommonAncestor(root.left, p, q)\n",
    "            root.right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "            if root.left and root.right:\n",
    "                return root\n",
    "            if not root.left and not root.right:\n",
    "                return None\n",
    "            return root.left if root.left else root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "\n",
    "        root.left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        root.right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if root.left and root.right:\n",
    "            return root\n",
    "        elif root.left and not root.right:\n",
    "            return root.left\n",
    "        elif not root.left and root.right:\n",
    "            return root.right\n",
    "        else:\n",
    "            return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "\n",
    "        while True:\n",
    "            if root.val <p.val and root.val < q.val:\n",
    "                root = root.right\n",
    "            elif root.val > p.val and root.val > q.val:\n",
    "                root = root.left\n",
    "            else:\n",
    "                return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        if root is None:\n",
    "            return root\n",
    "        if root == p or root == q:\n",
    "            return root\n",
    "        # 确保p值小于q值\n",
    "        if p.val > q.val:\n",
    "            p, q = q, p\n",
    "        res = None\n",
    "        if root.val < p.val:\n",
    "            res = self.lowestCommonAncestor(root.right, p, q)\n",
    "            if res:\n",
    "                return res\n",
    "        elif root.val > q.val:\n",
    "            res = self.lowestCommonAncestor(root.left, p, q)\n",
    "            if res:\n",
    "                return res\n",
    "        else:\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        x=root.val\n",
    "        if p.val<x and q.val<x:\n",
    "            return self.lowestCommonAncestor(root.left,p,q)\n",
    "        if p.val>x and q.val>x:\n",
    "            return self.lowestCommonAncestor(root.right,p,q)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        if (root.val >  p.val ) and (root.val >  q.val) :# p,q都在左子树\n",
    "            return self.lowestCommonAncestor(root.left,p,q)\n",
    "\n",
    "        elif (root.val < p.val )and (root.val < q.val) : # p,q都在右子树\n",
    "            return self.lowestCommonAncestor(root.right,p,q)\n",
    "\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getfathers(self, root):\n",
    "        dic = dict()\n",
    "        if not root:\n",
    "            return dic\n",
    "        dic[root.left] = root\n",
    "        dic[root.right] = root\n",
    "        dic.update(self.getfathers(root.left))\n",
    "        dic.update(self.getfathers(root.right))\n",
    "        return dic\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        dic = {root: root}\n",
    "        dic.update(self.getfathers(root))\n",
    "        cur = p\n",
    "        P_fathers = []\n",
    "        while cur != dic[cur]:\n",
    "            P_fathers.append(cur)\n",
    "            cur = dic[cur]\n",
    "        P_fathers.append(root)\n",
    "        cur1 = q\n",
    "        while cur1 != dic[cur1]:\n",
    "            if cur1 in P_fathers:\n",
    "                return cur1\n",
    "            cur1 = dic[cur1]\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        print(root)\n",
    "        if p.val > q.val:\n",
    "            p, q = q, p\n",
    "        if p.val <= root.val and root.val <= q.val:\n",
    "            return root\n",
    "        else:\n",
    "            if p.val < root.val and q.val < root.val:\n",
    "                return self.lowestCommonAncestor(root.left, p, q)\n",
    "            else:\n",
    "                return self.lowestCommonAncestor(root.right, p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        while root:\n",
    "            if root.val > p.val and root.val > q.val:\n",
    "                root = root.left\n",
    "            elif root.val < p.val and root.val < q.val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                return root\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "        def DFS(root,path):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root)\n",
    "            if root == p:\n",
    "                path_p.extend(path)\n",
    "            if root == q:\n",
    "                path_q.extend(path)\n",
    "            DFS(root.left,path)\n",
    "            DFS(root.right,path)\n",
    "            path.pop()\n",
    "        \n",
    "        path_p = []\n",
    "        path_q = []\n",
    "        path = []\n",
    "        DFS(root,path)\n",
    "\n",
    "        n = len(path_p)\n",
    "        m = len(path_q)\n",
    "        iter_num = n if n<m else m\n",
    "        for i in range(iter_num):\n",
    "            if path_p[i] != path_q[i]:\n",
    "                return path_p[i-1]\n",
    "        if iter_num == n:\n",
    "            return path_p[-1]\n",
    "        else:\n",
    "            return path_q[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
